package offer;

import java.util.*;

/**
 * @Author Elephas
 * @Date 2022/1/29
 **/
@FunctionalInterface
public interface PermuteUnique {
    List<List<Integer>> permuteUnique(int[] nums);
}
class PermuteUniqueImpl1 implements PermuteUnique{

    @Override
    public List<List<Integer>> permuteUnique(int[] nums) {
        Set<Integer> integers = new HashSet<>();
        int[] stack = new int[nums.length];
        int top = 0;
        boolean[] isVisited = new boolean[nums.length];
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < isVisited.length; i++) {
            isVisited[i] = false;
        }
        trackBack(stack,isVisited,nums,ans,top);
        return ans;

    }
    private void trackBack(int[] stack,boolean[] isVisited,int[] nums,List<List<Integer>> ans,int top){
        if(top == stack.length){
            List<Integer> item = new LinkedList<>();
            for (int i = 0; i < stack.length; i++) {
                item.add(stack[i]);
            }
            ans.add(item);
            return;
        }else{
            Set<Integer> hashSet = new HashSet<>();
            for (int i = 0; i < isVisited.length; i++) {
                if(!isVisited[i] && !hashSet.contains(nums[i])){
                    hashSet.add(nums[i]);
                    stack[top ++] = nums[i];
                    isVisited[i] = true;
                    trackBack(stack,isVisited,nums,ans,top);
                    top--;
                    isVisited[i] = false;
                }
            }
            return;
        }
    }
}

class PermuteUniqueImpl2 implements PermuteUnique{
    static final int[] TEST_01 = new int[]{1,1,2};

    public static void main(String[] args) {
        new PermuteUniqueImpl2().permuteUnique(TEST_01);
    }
    @Override
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int[] stack = new int[nums.length];
        int top = 0;
        boolean[] isVisited = new boolean[nums.length];
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < isVisited.length; i++) {
            isVisited[i] = false;
        }
        trackBack(stack,isVisited,nums,ans,top);
        return ans;

    }
    private void trackBack(int[] stack,boolean[] isVisited,int[] nums,List<List<Integer>> ans,int top){
        if(top == stack.length){
            List<Integer> item = new LinkedList<>();
            for (int i = 0; i < stack.length; i++) {
                item.add(stack[i]);
            }
            ans.add(item);
            return;
        }else{

            for (int i = 0; i < isVisited.length; i++) {
                // 关键是当前访问元素的前驱未被访问过，说明已经重置过了，否则
                if(i > 0 && !isVisited[i - 1] && nums[i] == nums[i-1]){
                    continue;
                }
                if(!isVisited[i] ){
                    stack[top ++] = nums[i];
                    isVisited[i] = true;
                    trackBack(stack,isVisited,nums,ans,top);
                    top--;
                    isVisited[i] = false;
                }
            }
            return;
        }
    }
}